import functools


class Solution(object):
    def minDifficulty(self, jobDifficulty, d):
        n = len(jobDifficulty)

        @functools.cache
        def dfs(k, t):
            if t == 1:
                return max(jobDifficulty[: k])
            else:
                now_max = 0
                now_val = float('inf')
                for j in range(k - 1, t - 2, -1):
                    now_max = max(now_max, jobDifficulty[j])
                    now_val = min(now_val, now_max + dfs(j, t - 1))
                return now_val

        if n < d:
            return -1

        return dfs(n, d)


data = Solution()
jobDifficulty = [6, 5, 4, 3, 2, 1]
d = 2
print(data.minDifficulty(jobDifficulty, d))
